#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
/*
 * @lc app=leetcode.cn id=51 lang=cpp
 *
 * [51] N 皇后
 */

// @lc code=start
class Solution {
public:
    vector<vector<string>> res;
    vector<vector<string>> solveNQueens(int n) {
        vector<bool> used(n, false); vector<string> temp;
        vector<bool> right(2 * n, false); vector<bool> left(2 * n, false);
        dfs(0, n, temp, used, right, left);
        return res;
    }

    void dfs(int c, int n, vector<string>& now, vector<bool>& used, vector<bool>& right, vector<bool>& left) {
        if (c == n) {
            res.push_back(now);
            return;
        }
        string x(n, '.');
        for (int i = 0; i < n; i++) {
            if (!used[i] && !right[i - c + n] && !left[i + c]) {
                x[i] = 'Q'; used[i] = true;
                right[i - c + n] = true; left[i + c] = true;
                now.push_back(x);
                dfs(c + 1, n, now, used, right, left);
                x[i] = '.'; used[i] = false;
                right[i - c + n] = false; left[i + c] = false;
                now.pop_back();
            }
        }
        
    }
};
// @lc code=end

